package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:47 AM
 *
 * https://leetcode-cn.com/problems/edit-distance/
 */
public class _72_编辑距离 {

    public int minDistance(String word1, String word2) {

        if (word1 == null || word2 == null) {

            return 0;
        }
        if (word1.length() * word2.length() == 0) {

            return word1.length() + word2.length();
        }

        char[] wc1 = word1.toCharArray();
        char[] wc2 = word2.toCharArray();

        if (wc1.length < wc2.length) {

            char[] tmp = wc1;
            wc1 = wc2;
            wc2 = tmp;
        }

        int[] dp = new int[wc2.length + 1];

        for (int i = 0; i < dp.length; i++) {

            dp[i] = i;
        }

        int pre;
        for (int i = 1; i <= wc1.length; i++) {

            pre = dp[0];
            dp[0] = i;
            for (int j = 1; j <= wc2.length; j++) {

                int cur = pre;
                pre = dp[j];

                if (wc1[i - 1] != wc2[j - 1]) {
                    cur++;
                }
                dp[j] = Math.min(cur,Math.min(dp[j - 1] + 1,dp[j]+ 1));
            }

        }

        return dp[wc2.length];
    }
}
